package search;

/**
 * @description:
 * @author: w_jingbo
 * @date: 2023/9/15
 * @Copyright: 博客：http://coisini.wang
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,2,2,2,3,5,7,9}  ;
        int index = nearestIndex2(arr,arr.length,2);
        System.out.println(index);
    }

    /**
     * 题目2：在有序数组中找出>=value 的最左位置
     *
     * 例如 [1,2,2,2,2,3,5,7,9],>=2的最左位置即下标2
     * @param arr
     * @param n
     * @param val
     * @return
     */
    public static int nearestIndex(int[] arr, int n, int val) {

        int L = 0;
        int R = n - 1;
        // 记录最左的对号
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= val) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;

    }


    public static int equalIndex(int[] arr, int n, int val) {

        int L = 0;
        int R = n - 1;
        // 记录最左的对号
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] == val) {
                index = mid;
                return index;

            }else if(arr[mid] > val){
                index = mid;
                R = mid - 1;
            }else{
                L = mid + 1;
            }
        }
        return index;

    }

    public static int nearestIndex2(int[] arr,int n , int value) {
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] <= value) {
                index = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return index;
    }
}
